<!DOCTYPE html>
<html>
<head>
	<title>背包问题</title>
</head>
<body>
<script type="text/javascript">
/*
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
    物品 A B C D E F G
    重量 35 30 60 50 40 10 25
    价值 10 40 30 50 35 40 30
*/
const target = [{
	name: 'A',
	val1: 35,
	val2: 10,
},{
	name: 'B',
	val1: 30,
	val2: 40,
},{
	name: 'C',
	val1: 60,
	val2: 30,
},{
	name: 'D',
	val1: 50,
	val2: 50,
},{
	name: 'E',
	val1: 40,
	val2: 35,
},{
	name: 'F',
	val1: 10,
	val2: 40,
},{
	name: 'G',
	val1: 25,
	val2: 30,
}];
const capacity = 150;//背包容量
</script>
<script type="text/javascript">
//贪心策略:选取价值最大者
const sortFn1 = (arr1, capacity1) => {
	let arr2 = JSON.parse(JSON.stringify(arr1));
	let ret = [];
	let capacity2 = capacity1;//剩余容量
	let total = 0;

	arr2.sort((a, b) => {
		return b.val2 - a.val2;
	});
	arr2.map((cur, index) => {
		let num = parseInt(capacity2 / cur.val1);//剩余重量能否放下当前元素
		if(num) {
			capacity2 -= cur.val1;
			total += cur.val2;
			ret.push(cur);
		}
	});
	console.log('arr2:', arr2);
	console.log('total:', total);
	return ret;
};
console.log('sortFn1:', sortFn1(target, capacity));
</script>
<script type="text/javascript">
//贪心策略:选取比率最大者
const sortFn2 = (arr1, capacity1) => {
	let arr2 = JSON.parse(JSON.stringify(arr1));
	let ret = [];
	let capacity2 = capacity1;//剩余容量
	let total = 0;

	arr2.sort((a, b) => {
		return (b.val2 / b.val1) - (a.val2 / a.val1);
	});
	arr2.map((cur, index) => {
		let num = parseInt(capacity2 / cur.val1);//剩余重量能否放下当前元素
		if(num) {
			capacity2 -= cur.val1;
			total += cur.val2;
			ret.push(cur);
		}
	});
	console.log('arr2:', arr2);
	console.log('total:', total);
	return ret;
};
console.log('sortFn2:', sortFn2(target, capacity));
</script>
</body>
</html>